package leetcode.D100.T18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-25 15:01:05 星期五
 */

class Solution {
    /**
     * 一刷
     * 解法：四数之和就是遍历求三数之和
     * 这里对n数之和的解法做了统一接口，n>2时遍历求(n-1)数之和，n=2时用双指针
     * 复杂度：时间复杂度，两重循环*双指针，即O(n^3)
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return nSum(nums, 0, target, 4);
    }

    private List<List<Integer>> nSum(int[] nums, int start, int target, int n) {
        List<List<Integer>> results = new ArrayList<>();
        if (n > 2) {
            for(int i=start; i<nums.length-n+1; ++i) {
                if (i > start && nums[i] == nums[i-1])
                    continue;
                List<List<Integer>> temp = nSum(nums, i + 1, target - nums[i], n-1);
                for (List<Integer> result : temp) {
                    result.add(nums[i]);
                    results.add(result);
                }
            }
        } else {
            int left = start, right = nums.length-1;
            while(left < right) {
                int sum = nums[left] + nums[right];
                int leftBase = nums[left], rightBase = nums[right];
                if (sum < target) {
                    while (left < right && nums[left] == leftBase)
                        left++;
                } else if (sum > target) {
                    while (left < right && nums[right] == rightBase)
                        right--;
                } else {
                    List<Integer> result = new ArrayList<>();
                    result.add(nums[left]);
                    result.add(nums[right]);
                    results.add(result);
                    while (left < right && nums[left] == leftBase)
                        left++;
                    while (left < right && nums[right] == rightBase)
                        right--;
                }
            }
        }
        return results;
    }
}